//https://leetcode.cn/problems/range-sum-of-bst/submissions/504812538/?envType=daily-question&envId=2024-02-26



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int _rangeSumBST(TreeNode* root, int low, int high, int &ans)
    {
        if(root == nullptr) return 0;
        
        int left_sum = _rangeSumBST(root->left, low, high, ans);
        int right_sum = _rangeSumBST(root->right, low, high, ans);

        if(root->val >= low && root->val <= high) {
            ans += root->val; // 如果当前节点在指定范围内，则加上该节点的值
        }
        
        return left_sum + right_sum + (root->val >= low && root->val <= high ? root->val : 0);
    }

    int rangeSumBST(TreeNode* root, int low, int high) {
        int ans = 0;
        _rangeSumBST(root, low, high, ans);
        return ans;
    }
};
